#ifndef MKAHYPAR_HYPERGRAPH_H
#define MKAHYPAR_HYPERGRAPH_H

#include <limits>
#include "mkahypar/utils/typedef.h"
#include "mkahypar/utils/mandatory.h"
#include "mkahypar/utils/empty.h"
#include "mkahypar/utils/macros.h"
#include "mkahypar/utils/math.h"
#include "mkahypar/datastructure/fpga_graph.h"
#include "mkahypar/datastructure/fast_reset_flag_array.h"
#include "mkahypar/datastructure/bitset.h"
#include "mkahypar/datastructure/robin_hood.h"
#include "mkahypar/partition/metrics.h"

namespace mkahypar {
  namespace ds {
// ! Helper function to allow range-based for loops
    template<typename Iterator>
    Iterator begin(const std::pair<Iterator, Iterator> &x) {
      return x.first;
    }

// ! Helper function to allow range-based for loops
    template<typename Iterator>
    Iterator end(const std::pair<Iterator, Iterator> &x) {
      return x.second;
    }

    template<typename HypernodeType_ = Mandatory,
            typename HyperedgeType_ = Mandatory,
            typename HypernodeWeightType_ = Mandatory,
            typename HyperedgeWeightType_ = Mandatory,
            typename PartitionIDType_ = Mandatory,
            class HypernodeData_ = meta::Empty,
            class HyperedgeData_ = meta::Empty>
    class GenericHypergraph {
    public:
      using HypernodeID = HypernodeType_;
      using HyperedgeID = HyperedgeType_;
      using PartitionID = PartitionIDType_;
      using HypernodeWeight = HypernodeWeightType_;
      using HyperedgeWeight = HyperedgeWeightType_;
      using HypernodeData = HypernodeData_;
      using HyperedgeData = HyperedgeData_;
      //平行边检测
      static constexpr size_t kEdgeHashSeed = 42;
      //非法分区标识
      static constexpr HypernodeID kInvalidCount = std::numeric_limits<HypernodeID>::max();


    private:
      //存储超点的类型
      struct HypernodeTraits {
        using WeightType = HypernodeWeight;
        using IDType = HypernodeID;
      };
      //存储超边的类型
      struct HyperedgeTraits {
        using WeightType = HyperedgeType_;
        using IDType = HyperedgeID;
      };
      //超点辅助数据结构
      struct AdditionalHypernodeData : public HypernodeData {
        //所在分区
        PartitionID part_id = kInvalidPartition;
        //切边数目
        HyperedgeID num_incident_cut_hes = 0;
        //搜索状态
        uint32_t state = 0;
        //记录多少个点缩合在一起
        int64_t count = 1;
      };
      //超边辅助数据结构
      struct AdditionalHyperedgeData : public HyperedgeData_ {
        //二进制表示连接了哪些分区
        Bitset connectivity;
        //边的hash值
        size_t hash = kEdgeHashSeed;
      };

      //定义超点
      template<typename ElementTypeTraits, class HypergraphElementData>
      class Vertex : public HypergraphElementData {
      public:
        using WeightType = typename ElementTypeTraits::WeightType;
        using IDType = typename ElementTypeTraits::IDType;

        Vertex() :
                _incident_nets(),
                _weight(8) {}

        Vertex(NodeResource &weight) :
                _incident_nets(),
                _weight(weight) {}

        Vertex(Vertex &) = default;

        Vertex &operator=(const Vertex &) = default;

        Vertex(Vertex &&) = default;

        Vertex &operator=(Vertex &&) = default;

        ~Vertex() = default;

        // ! Disables the hypernode/hyperedge. Disable hypernodes/hyperedges will be skipped
        // ! when iterating over the set of all nodes/edges.
        void disable() {
          _valid = false;
        }

        bool isDisabled() const {
          return _valid == false;
        }

        void enable() {
          _valid = true;
        }

        //返回邻接超边的数目
        IDType size() const {
          return _incident_nets.size();
        }

        //返回资源种类
        IDType resourceSize() {
          return _weight.size();
        }

        //返回资源
        NodeResource &weight() {
          return _weight;
        }

        void setWeight(NodeResource &weight) {
          _weight = weight;
        }

        //返回邻接超边
        std::vector<HyperedgeID> &incidentNets() {
          return _incident_nets;
        }

        const std::vector<HyperedgeID> &incidentNets() const {
          return _incident_nets;
        }

        //重载==
        bool operator==(Vertex &rhs) {
          return _incident_nets.size() == rhs._incident_nets.size() &&
                 _weight == rhs._weight &&
                 _valid == rhs._valid &&
                 std::is_permutation(_incident_nets.begin(),
                                     _incident_nets.end(),
                                     rhs._incident_nets.begin());
        }

        bool operator!=(const Vertex &rhs) const {
          return !operator==(this, rhs);
        }

      private:
        //记录邻接超边
        std::vector<HyperedgeID> _incident_nets;
        //记录资源数组
        NodeResource _weight;
        bool _valid = true;
      };

      //定义超边
      template<typename ElementTypeTraits, class HypergraphElementData>
      class HyperEdge : public HypergraphElementData {
      public:
        using WeightType = typename ElementTypeTraits::WeightType;
        using IDType = typename ElementTypeTraits::IDType;

        HyperEdge(const IDType begin, const IDType size,
                  const WeightType weight) :
                _begin(begin),
                _size(size),
                _weight(weight) {}

        HyperEdge() = default;

        HyperEdge(const HyperEdge &) = default;

        HyperEdge &operator=(const HyperEdge &) = default;

        HyperEdge(HyperEdge &&) = default;

        HyperEdge &operator=(HyperEdge &&) = default;

        ~HyperEdge() = default;


        void disable() {
          _valid = false;
        }

        bool isDisabled() const {
          return _valid == false;
        }

        void enable() {
          _valid = true;
        }

        //返回源节点
        IDType source() const {
          return _source;
        }

        void setSource(IDType source) {
          _source = source;
        }

        // ! Returns the index of the first element in _incidence_array
        IDType firstEntry() const {
          return _begin;
        }

        // ! Sets the index of the first element in _incidence_array to begin
        void setFirstEntry(IDType begin) {
          _begin = begin;
          _valid = true;
        }

        // ! Returns the index of the first element in _incidence_array
        IDType firstInvalidEntry() const {
          return _begin + _size;
        }

        IDType size() const {
          return _size;
        }

        void setSize(IDType size) {
          _size = size;
        }


        void incrementSize() {
          ++_size;
        }

        void decrementSize() {
          --_size;
        }

        WeightType weight() const {
          return _weight;
        }

        void setWeight(WeightType weight) {
          _weight = weight;
        }

        bool operator==(const HyperEdge &rhs) const {
          return _begin == rhs._begin && _size == rhs._size && _weight == rhs._weight;
        }

        bool operator!=(const HyperEdge &rhs) const {
          return !operator==(this, rhs);
        }

      private:
        //source节点
        IDType _source;
        // ! Index of the first element in _incidence_array
        IDType _begin = 0;
        // ! Number of _incidence_array elements
        IDType _size = 0;
        // ! Hypernode/Hyperedge weight
        WeightType _weight = 1;
        // ! Flag indicating whether or not the element is active.
        bool _valid = true;
      };

      //访问迭代器，支持for range遍历
      template<typename ElementType>
      class HypergraphElementIterator :
              public std::iterator<std::forward_iterator_tag,    // iterator_category
                      typename ElementType::IDType,   // value_type
                      std::ptrdiff_t,   // difference_type
                      const typename ElementType::IDType *,   // pointer
                      typename ElementType::IDType> {   // reference
        using IDType = typename ElementType::IDType;

      public:
        HypergraphElementIterator() = default;

        HypergraphElementIterator(const HypergraphElementIterator &other) = default;

        HypergraphElementIterator &operator=(const HypergraphElementIterator &other) = default;

        HypergraphElementIterator(HypergraphElementIterator &&other) = default;

        HypergraphElementIterator &operator=(HypergraphElementIterator &&other) = default;

        ~HypergraphElementIterator() = default;

        /*!
         * Construct a HypergraphElementIterator
         * See GenericHypergraph::nodes() or GenericHypergraph::edges() for usage.
         *
         * If start_element is invalid, the iterator advances to the first valid
         * element.
         *
         * \param start_element A pointer to the starting position
         * \param id The index of the element the pointer points to
         * \param max_id The maximum index allowed
         */
        HypergraphElementIterator(const ElementType *start_element, IDType id, IDType max_id) :
                _id(id),
                _max_id(max_id),
                _element(start_element) {
          if (_id != _max_id && _element->isDisabled()) {
            operator++();
          }
        }

        // ! Returns the id of the element the iterator currently points to.
        IDType operator*() const {
          return _id;
        }

        // ! Prefix increment. The iterator advances to the next valid element.
        HypergraphElementIterator &operator++() {
          do {
            ++_id;
            ++_element;
          } while (_id < _max_id && _element->isDisabled());
          return *this;
        }

        // ! Postfix increment. The iterator advances to the next valid element.
        HypergraphElementIterator operator++(int) {
          HypergraphElementIterator copy = *this;
          operator++();
          return copy;
        }

        // ! Convenience function for range-based for-loops
        friend HypergraphElementIterator end<>(const std::pair<HypergraphElementIterator,
                HypergraphElementIterator> &iter_pair);

        // ! Convenience function for range-based for-loops
        friend HypergraphElementIterator begin<>(const std::pair<HypergraphElementIterator,
                HypergraphElementIterator> &iter_pair);

        bool operator!=(const HypergraphElementIterator &rhs) {
          return _id != rhs._id;
        }

        bool operator==(const HypergraphElementIterator &rhs) {
          return _id == rhs._id;
        }

      private:
        // Handle to the HypergraphElement the iterator currently points to
        IDType _id = 0;
        // Maximum allowed index
        const IDType _max_id = 0;
        // HypergraphElement the iterator currently points to
        const ElementType *_element = nullptr;
      };

    public:
      // ! The data type used to incident nets of vertices and pins of nets
      using VertexID = uint32_t;
      // 超点的数据类型
      using Hypernode = Vertex<HypernodeTraits, AdditionalHypernodeData>;
      // 超边类型
      using Hyperedge = HyperEdge<HyperedgeTraits, AdditionalHyperedgeData>;
      using PinHandleIterator = typename std::vector<VertexID>::iterator;
      using IncidenceIterator = typename std::vector<VertexID>::const_iterator;
      using HypernodeIterator = HypergraphElementIterator<const Hypernode>;
      using HyperedgeIterator = HypergraphElementIterator<const Hyperedge>;
      using Map = robin_hood::unordered_map<HypernodeID, int64_t>;
      //缩合备忘录
      struct Memento {
        const HypernodeID u;
        const HypernodeID v;
      };
      struct PartInfo {

      };

      using ContractionMemento = Memento;


      //构造函数
      GenericHypergraph() :
              _num_hyperedges(0), _num_hypernodes(0) {

      }

      //输入的时候执行初始话
      void initialize(int part_num, HypernodeID nums_pin) {
        _initial_num_hypernodes = _num_hypernodes;
        _initial_num_hyperedges = _num_hyperedges;
        _initial_num_pins = nums_pin;
        _k = part_num;//分区数
        _pins_in_part.resize(_num_hyperedges * _k);//统计超边在每个分区的pin count
        _part_route_count.resize(_num_hyperedges, std::vector<int64_t>(_k));
        _tar_route_count.resize(_num_hyperedges);
        _hes_not_containing_u.initialize(_initial_num_hyperedges);
        _hes_v_is_source.initialize(_initial_num_pins);
      }

      //创建超点
      inline void createHyperNode(NodeResource &weight) {
        _hypernodes.emplace_back(weight);
        ++_num_hypernodes;
      }

      //创建超边
      inline void createHyperEdge() {
        _hyperedges.emplace_back(0, 0, 1);
        ++_num_hyperedges;
      }

      //访问
      const Hypernode &hypernode(const HypernodeID u) const {
        return _hypernodes[u];
      }

      // ! Accessor for hyperedge-related information
      const Hyperedge &hyperedge(const HyperedgeID e) const {
        return _hyperedges[e];
      }

      // ! To avoid code duplication we implement non-const version in terms of const version
      Hypernode &hypernode(const HypernodeID u) {
        return const_cast<Hypernode &>(static_cast<const GenericHypergraph &>(*this).hypernode(u));
      }

      // ! To avoid code duplication we implement non-const version in terms of const version
      Hyperedge &hyperedge(const HyperedgeID e) {
        return const_cast<Hyperedge &>(static_cast<const GenericHypergraph &>(*this).hyperedge(e));
      }

      //for range 访问超边的pins
      std::pair<IncidenceIterator, IncidenceIterator> pins(const HyperedgeID e) const {
        return std::make_pair(_incidence_array.cbegin() + hyperedge(e).firstEntry(),
                              _incidence_array.cbegin() + hyperedge(e).firstInvalidEntry());
      }

      std::pair<PinHandleIterator, PinHandleIterator> pinHandles(const HyperedgeID he) {
        return std::make_pair(_incidence_array.begin() + hyperedge(he).firstEntry(),
                              _incidence_array.begin() + hyperedge(he).firstInvalidEntry());
      }

      //访问所有超点
      std::pair<HypernodeIterator, HypernodeIterator> nodes() const {
        return std::make_pair(HypernodeIterator(_hypernodes.data(), 0, _initial_num_hypernodes),
                              HypernodeIterator((_hypernodes.data() + _initial_num_hypernodes),
                                                _initial_num_hypernodes, _initial_num_hypernodes));
      }

      //访问所有超边
      std::pair<HyperedgeIterator, HyperedgeIterator> edges() const {
        return std::make_pair(HyperedgeIterator(_hyperedges.data(), 0, _initial_num_hyperedges),
                              HyperedgeIterator((_hyperedges.data() + _initial_num_hyperedges),
                                                _initial_num_hyperedges, _initial_num_hyperedges));
      }

      //访问节点邻接超边
      std::pair<IncidenceIterator, IncidenceIterator> incidentEdges(const HypernodeID u) const {
        return std::make_pair(hypernode(u).incidentNets().cbegin(),
                              hypernode(u).incidentNets().cend());
      }

      //移除一条单点边
      void removeEdge(const HyperedgeID he) {
        for (const HypernodeID &pin: pins(he)) {
          removeIncidentEdgeFromHypernode(he, pin);
        }
        hyperedge(he).disable();
        invalidatePartitionPinCounts(he);
        --_num_hyperedges;
      }

      //删除一条平行边，更改路由
      void removeEdge(const HyperedgeID he, const HyperedgeID representative) {
        for (const HypernodeID &pin: pins(he)) {
          removeIncidentEdgeFromHypernode(he, pin);//pin移除超边
          if (pin != hyperedge(he).source()) {
            _tar_route_count[representative][pin] += _tar_route_count[he][pin];
          }
        }
        hyperedge(he).disable();
        invalidatePartitionPinCounts(he);
        --_num_hyperedges;
      }

      //恢复单点超边
      void restoreEdge(const HyperedgeID he) {
        ++_num_hyperedges;
        hyperedge(he).enable();
        resetPartitionPinCounts(he);
        for (const HypernodeID &pin: pins(he)) {
//          LOG<<pin<<he;
          hypernode(pin).incidentNets().push_back(he);
          if (partID(pin) != kInvalidPartition) {
            incrementPinCountInPart(he, partID(pin));
          }
        }
      }

      //恢复超边，由于平行边移除导致的,需要维护超点的切边是否准确
      void restoreEdge(const HyperedgeID he, const HyperedgeID old_representative) {
        ++_num_hyperedges;
        hyperedge(he).enable();
        resetPartitionPinCounts(he);
        for (const HypernodeID &pin: pins(he)) {
          hypernode(pin).incidentNets().push_back(he);
          if (partID(pin) != kInvalidPartition) {
            incrementPinCountInPart(he, partID(pin));
          }
          if (pin != hyperedge(he).source()) {
            //更改路由
            int64_t count = _tar_route_count[he][pin];
            _tar_route_count[old_representative][pin] -= count;
            _part_route_count[old_representative][partID(pin)] -= count;
            _part_route_count[he][partID(pin)] += count;
          }

          if (connectivity(old_representative) > 1) {
            ++hypernode(pin).num_incident_cut_hes;
          }
        }
      }

      //恢复超边，由于平行边移除导致的,需要维护超点的切边是否准确
      template<class HopPenaltyPolicy = Mandatory>
      void restoreEdge(const HyperedgeID he, const HyperedgeID old_representative, Metrics &best, FPGAGraph &topo) {
        ++_num_hyperedges;
        hyperedge(he).enable();
        resetPartitionPinCounts(he);
        int64_t old_hop_gain = 0, new_hop_gain = 0;
        //计算old_hop_gain
        PartitionID source_part = partID(hyperedge(he).source());
        for (PartitionID id = 0; id < _k; ++id) {
//            LOG << "pin:" << pin << old_representative << id << edgeWeight(old_representative) << topo._distance[
//                    source_part][id] << _part_route_count[old_representative][id];
          old_hop_gain += HopPenaltyPolicy::compute(edgeWeight(old_representative), topo._distance[
                  source_part][id]) * _part_route_count[old_representative][id];
        }
        for (const HypernodeID &pin: pins(he)) {
          hypernode(pin).incidentNets().push_back(he);
          if (partID(pin) != kInvalidPartition) {
            incrementPinCountInPart(he, partID(pin));
          }
          if (pin != hyperedge(he).source()) {
            //更改路由
            int64_t count = _tar_route_count[he][pin];
            _tar_route_count[old_representative][pin] -= count;
            _part_route_count[old_representative][partID(pin)] -= count;
            _part_route_count[he][partID(pin)] += count;
          }

          if (connectivity(old_representative) > 1) {
            ++hypernode(pin).num_incident_cut_hes;
          }
        }
        //计算new_hop_gain
        for (PartitionID id = 0; id < _k; ++id) {
          new_hop_gain += HopPenaltyPolicy::compute(edgeWeight(old_representative) - edgeWeight(he), topo._distance[
                  source_part][id]) * _part_route_count[old_representative][id]
                          +
                          HopPenaltyPolicy::compute(edgeWeight(he), topo._distance[
                                  source_part][id]) * _part_route_count[he][id];
        }
//        LOG << old_hop_gain << new_hop_gain;
        best.hop_penalty += new_hop_gain - old_hop_gain;
        best.updateObj();
      }

      //part增加超边的pin
      bool incrementPinCountInPart(const HyperedgeID he, const PartitionID id) {
        const size_t offset = static_cast<size_t>(he) * _k + id;
        _pins_in_part[offset] += 1;
        const bool connectivity_increased = _pins_in_part[offset] == 1;
        if (connectivity_increased) {
          hyperedge(he).connectivity.add(id);
        }
        return connectivity_increased;
      }

      //part减少超边的pin
      bool decrementPinCountInPart(const HyperedgeID he, const PartitionID id) {
        const size_t offset = static_cast<size_t>(he) * _k + id;
        _pins_in_part[offset] -= 1;
        const bool connectivity_decreased = _pins_in_part[offset] == 0;
        if (connectivity_decreased) {
          hyperedge(he).connectivity.remove(id);
        }
        return connectivity_decreased;
      }

      //part增加route count
      void incrementRouteCountInPart(const HyperedgeID he, const PartitionID id, const HypernodeID hn) {
        _part_route_count[he][id] += _tar_route_count[he][hn];
      }

      //part减少route count
      void decrementRouteCountInPart(const HyperedgeID he, const PartitionID id, const HypernodeID hn) {
        _part_route_count[he][id] -= _tar_route_count[he][hn];
      }

      //计算超边再part上的pin的size个数
      HypernodeID pinCountInPart(const HyperedgeID he, const PartitionID id) const {
        return _pins_in_part[static_cast<size_t>(he) * _k + id];
      }

      int64_t routeCountInPart(const HyperedgeID he, const PartitionID id) const {
        return _part_route_count[he][id];
      }


      //计算超边再part上targer hn的pin的个数
      int64_t tarRouteCount(const HyperedgeID he, const HypernodeID hn) {
        return _tar_route_count[he][hn];
      }

      //使超边he所在的part的pin count无效
      void invalidatePartitionPinCounts(const HyperedgeID he) {
        for (PartitionID part = 0; part < _k; ++part) {
          _pins_in_part[static_cast<size_t>(he) * _k + part] = kInvalidCount;
        }
        hyperedge(he).connectivity.clear();
//        _connectivity_sets[he].clear();
      }

      //恢复超边he的pin count
      void resetPartitionPinCounts(const HyperedgeID he) {
        for (PartitionID part = 0; part < _k; ++part) {
          _pins_in_part[static_cast<size_t>(he) * _k + part] = 0;
          _part_route_count[he][part] = 0;
        }
      }
      //超点hn移除超边索引he
      MKAHYPAR_ATTRIBUTE_ALWAYS_INLINE void removeIncidentEdgeFromHypernode(const HyperedgeID he,
                                                                            const HypernodeID hn) {
        using std::swap;
        auto begin = hypernode(hn).incidentNets().begin();
        auto last_entry = hypernode(hn).incidentNets().end() - 1;
        while (*begin != he) {
          ++begin;
        }
        swap(*begin, *last_entry);
        hypernode(hn).incidentNets().pop_back();
      }

      //缩合顶点对(u,v)
      Memento contract(const HypernodeID u, const HypernodeID v) {
        using std::swap;
        hypernode(u).weight() += hypernode(v).weight();
        hypernode(u).count += hypernode(v).count;
        //遍历v的邻居边
        for (const HyperedgeID he: hypernode(v).incidentNets()) {
          const HypernodeID pins_begin = hyperedge(he).firstEntry();
          const HypernodeID pins_end = hyperedge(he).firstInvalidEntry();
          const HypernodeID source = hyperedge(he).source();
          HypernodeID slot_of_u = pins_end - 1;
          HypernodeID last_pin_slot = pins_end - 1;

          for (HypernodeID pin_iter = pins_begin; pin_iter != last_pin_slot; ++pin_iter) {
            const HypernodeID pin = _incidence_array[pin_iter];
            if (pin == v) {
              swap(_incidence_array[pin_iter], _incidence_array[last_pin_slot]);
              --pin_iter;
            } else if (pin == u) {
              slot_of_u = pin_iter;
            }
          }


          if (slot_of_u != last_pin_slot) {
            //u,v的公共超边
            // Case 1:
            // Hyperedge e contains both u and v. Thus we don't need to connect u to e and
            // can just cut off the last entry in the edge array of e that now contains v.
            if (source == v) {
              //eg1. source是v
              _hes_v_is_source.set(last_pin_slot, true);//标记v曾经是源点
              hyperedge(he).setSource(u);
            } else {
              if (source != u) {
                //eg2.source != u
                _tar_route_count[he][u] += _tar_route_count[he][v];
              }
            }
            edgeHash(he) -= math::hash(v);//更新hash值
            hyperedge(he).decrementSize();//更新超边size
          } else {
            // Case 2:
            // Hyperedge e does not contain u. Therefore we  have to connect e to the representative u.
            // This reuses the pin slot of v in e's incidence array (i.e. last_pin_slot!)
            if (source == v)
              hyperedge(he).setSource(u);//更改源点
            else {
              _tar_route_count[he][u] = _tar_route_count[he][v];//不会增加路由
            }
            edgeHash(he) -= math::hash(v);//更新hash值
            edgeHash(he) += math::hash(u);

            //u新增v的私有边he
            _incidence_array[hyperedge(he).firstInvalidEntry() - 1] = u;
            hypernode(u).incidentNets().push_back(he);
          }
        }
        hypernode(v).disable();
        --_num_hypernodes;

        return Memento{u, v};
      }

      //还原一对顶点
      void uncontract(const Memento &memento) {
        //恢复顶点v
        hypernode(memento.v).enable();
        hypernode(memento.u).weight() -= hypernode(memento.v).weight();
        hypernode(memento.u).count -= hypernode(memento.v).count;
        ++_num_hypernodes;
        hypernode(memento.v).part_id = hypernode(memento.u).part_id;
        //标记v的所有超边
        _hes_not_containing_u.reset();
        for (const HyperedgeID &he: incidentEdges(memento.v)) {
          _hes_not_containing_u.set(he, true);
        }
        //遍历u的所有超边
        const auto &incident_hes_of_u = hypernode(memento.u).incidentNets();
        size_t incident_hes_end = incident_hes_of_u.size();
        for (size_t incident_hes_it = 0; incident_hes_it != incident_hes_end; ++incident_hes_it) {
          const HyperedgeID he = incident_hes_of_u[incident_hes_it];
          if (_hes_not_containing_u[he]) {
            const HypernodeID source = hyperedge(he).source();
            //eg1. u,v的公共边
            //eg2. v的私有边
//            LOG<<he<< _incidence_array[hyperedge(he).firstInvalidEntry()]<<memento.v<<hyperedge(he).firstInvalidEntry();
            if (hyperedge(he).firstInvalidEntry() < hyperedge(he + 1).firstEntry() &&
                _incidence_array[hyperedge(he).firstInvalidEntry()] == memento.v) {
              //eg1. u,v的公共边
//              LOG<<"common edge:"<<memento.u<<memento.v<<he;
              if (_hes_v_is_source[hyperedge(he).firstInvalidEntry()]) {
                //eg1.原来的source是v
                hyperedge(he).setSource(memento.v);//源点u->v
                _part_route_count[he][partID(memento.v)] += _tar_route_count[he][memento.u];
              } else {
                if (source == memento.u) {
                  //eg2.原来的source是u
                  _part_route_count[he][partID(memento.v)] += _tar_route_count[he][memento.v];
                } else {
                  //eg3.原来的source既不是u也不是v
                  _tar_route_count[he][memento.u] -= _tar_route_count[he][memento.v];
                }
              }

              hyperedge(he).incrementSize();//更新超边size
              incrementPinCountInPart(he, partID(memento.v));//更新part size信息
              if (connectivity(he) > 1)
                ++hypernode(memento.v).num_incident_cut_hes;     // because v is connected to that cut HE

            } else {
              //eg2. v的私有边
              std::swap(hypernode(memento.u).incidentNets()[incident_hes_it],
                        hypernode(memento.u).incidentNets().back());
              hypernode(memento.u).incidentNets().pop_back();
              --incident_hes_it;
              --incident_hes_end;
              //还原源点
              if (hyperedge(he).source() == memento.u) {
                //eg1.原来source是v
                hyperedge(he).setSource(memento.v);
              } else {
                //eg2.原来source不是v
                _tar_route_count[he].erase(memento.u);
              };
              //超边还原成指向v的
              resetReusedPinSlotToOriginalValue(he, memento);
              if (connectivity(he) > 1) {
                --hypernode(memento.u).num_incident_cut_hes;    // because u is not connected to that cut HE anymore
                ++hypernode(memento.v).num_incident_cut_hes;    // because v is connected to that cut HE
              }
            }
          }
        }
      }

      //重置超边连接
      void resetReusedPinSlotToOriginalValue(const HyperedgeID he, const Memento &memento) {
        PinHandleIterator pin_begin;
        PinHandleIterator pin_end;
        std::tie(pin_begin, pin_end) = pinHandles(he);
        --pin_end;
        while (*pin_end != memento.u) {
          --pin_end;
        }
        *pin_end = memento.v;
      }
      //还原一个备忘录
      MKAHYPAR_ATTRIBUTE_ALWAYS_INLINE void restoreMemento(const Memento &memento) {
        hypernode(memento.v).enable();
        ++_num_hypernodes;
        hypernode(memento.v).part_id = hypernode(memento.u).part_id;
//        ++_part_info[partID(memento.u)].size;
      }

      //重置边的hash值
      void resetEdgeHashes() {
        for (const HyperedgeID &he: edges()) {
          hyperedge(he).hash = kEdgeHashSeed;
          for (const HypernodeID &pin: pins(he)) {
            hyperedge(he).hash += math::hash(pin);
          }
        }
      }


      void reset() {
        _hes_v_is_source.reset();

        for (HypernodeID i = 0; i < _num_hypernodes; ++i) {
          hypernode(i).part_id = kInvalidPartition;
          hypernode(i).num_incident_cut_hes = 0;
        }
        for (auto hn: nodes()) {
          if (partID(hn) != kInvalidPartition)
            ERROREXIT("error!");
        }
        std::fill(_pins_in_part.begin(), _pins_in_part.end(), 0);
        //重置社区
        for (auto hn: nodes()) {
          _communities[hn] = partID(hn);
        }
        for (HyperedgeID i = 0; i < _num_hyperedges; ++i) {
          hyperedge(i).connectivity.clear();
          for (int j = 0; j < _k; ++j)
            _part_route_count[i][j] = 0;
          hyperedge(i).hash = kEdgeHashSeed;
          // not using pins(i) because it contains an assertion for hyperedge validity
          auto pins_begin = _incidence_array.cbegin() + hyperedge(i).firstEntry();
          const auto pins_end = _incidence_array.cbegin() + hyperedge(i).firstInvalidEntry();
          for (; pins_begin != pins_end; ++pins_begin) {
            const auto pin = *pins_begin;
            hyperedge(i).hash += math::hash(pin);
          }
        }
      }

      Map &edgeTarRouteCount(const HyperedgeID e) {
        return _tar_route_count[e];
      }

      //接口
      HyperedgeWeight edgeWeight(const HyperedgeID e) const {
        return hyperedge(e).weight();
      }

      void setEdgeWeight(const HyperedgeID e, const HyperedgeWeight weight) {
        hyperedge(e).setWeight(weight);
      }

      //超边hash值
      size_t &edgeHash(const HyperedgeID e) {
        return hyperedge(e).hash;
      }

      //超边 size
      HypernodeID edgeSize(const HyperedgeID e) const {
        return hyperedge(e).size();
      }

      //超点所在part
      PartitionID partID(const HypernodeID u) const {
        return hypernode(u).part_id;
      }

      //超边连接集个数
      PartitionID connectivity(const HyperedgeID he) {
        return hyperedge(he).connectivity.size();
      }

      //初始超点个数
      HypernodeID initialNumNodes() const {
        return _initial_num_hypernodes;
      }

      //初始超边个数
      HyperedgeID initialNumEdges() const {
        return _initial_num_hyperedges;
      }

      //初始超点个数
      HypernodeID currentNumNodes() const {
        return _num_hypernodes;
      }

      //初始超边个数
      HyperedgeID currentNumEdges() const {
        return _num_hyperedges;
      }

      HyperedgeID nodeDegree(const HypernodeID u) const {
        return hypernode(u).size();
      }

      //节点权重
      NodeResource &nodeWeight(HypernodeID u) {
        return hypernode(u).weight();
      }

      bool nodeIsEnabled(const HypernodeID u) const {
        return !hypernode(u).isDisabled();
      }

      bool edgeIsEnabled(const HyperedgeID e) const {
        return !hyperedge(e).isDisabled();
      }

      //是否是边界点
      bool isBorderNode(const HypernodeID hn) const {
        return hypernode(hn).num_incident_cut_hes > 0;
      }

      const std::vector<PartitionID> &communities() const {
        return _communities;
      }

      void setCommunities(std::vector<PartitionID> &&communities) {
        ASSERT(communities.size() == _current_num_hypernodes);
        _communities = std::move(communities);
      }

      //打印
      void printGraph() {
        LOG << "----------------------------------------------------";
        LOG << "current node:" << _num_hypernodes;
        LOG << "current edge:" << _num_hyperedges;
        LOG << "**********print node adj list:****************";
        for (auto v: nodes()) {
          LLOG << "node:" << v << "part:" << partID(v) << "nets:";
          for (auto adj: hypernode(v).incidentNets()) {
            LLOG << adj;
          }
          LOG << "";
        }
        LOG << "**********print node info:****************";
        for (auto v: nodes()) {
          LLOG << "node:" << v << "info:";
          hypernode(v).weight().print();
        }
        LOG << "**********print edge info:****************";
        for (auto e: edges()) {
          LLOG << "edge:" << e << "info:";
          std::cout << "weight = " << hyperedge(e).weight() << " and nets ";
          LLOG << hyperedge(e).source();
          for (const auto &t: pins(e)) {
            if (t != hyperedge(e).source())
              LLOG << t;
          }
          LOG << "";
        }


      }


      constexpr static PartitionID kInvalidPartition = -1;


      //初始所有超边pin的个数
      HypernodeID _initial_num_pins;
      //初始超点个数
      HypernodeID _initial_num_hypernodes;
      //初始超边个数
      HyperedgeID _initial_num_hyperedges;
      //当前超点个数
      HypernodeID _num_hypernodes;
      //当前超边个数
      HyperedgeID _num_hyperedges;
      //所有的超点
      std::vector<Hypernode> _hypernodes;
      //所有的超边
      std::vector<Hyperedge> _hyperedges;
      //所有的pin
      std::vector<VertexID> _incidence_array;
      //存储超边在每个part的pin size
      std::vector<HypernodeID> _pins_in_part;
      //存储每个超边target的每个pin的route count
      std::vector<Map> _tar_route_count;
      //存储超边在每个part上的route count
      std::vector<std::vector<int64_t>> _part_route_count;
      //还原的时候标记v的所有关联超边
      FastResetFlagArray<> _hes_not_containing_u;
      //记录公共边的源点
      FastResetFlagArray<> _hes_v_is_source;
      //社区
      std::vector<PartitionID> _communities;
      //划分分区数
      int _k;


    };
  }
}
#endif //MKAHYPAR_HYPERGRAPH_H
